#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

namespace lh
{
	//BM8 链表中倒数最后k个结点
	//https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=1377477&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 
    struct ListNode {
	    int val;
 	    struct ListNode *next;
        ListNode(int x) : val(x), next(nullptr) {}
    };

    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pHead, int k) {
            // write code here
            ListNode* fast = pHead;
            ListNode* slow = pHead;
            //快指针先走k步
            for (int i = 0; i < k; i++)
            {
                if (fast)
                {
                    fast = fast->next;
                }
                else {
                    return nullptr;
                }
            }
            //同时移动快慢指针，最终慢指针指向倒数结点
            while (fast)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;

        }
    };
    void test1()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(3);
        ListNode* node4 = new ListNode(4);
        ListNode* node5 = new ListNode(5);
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        ListNode* cur = node1;
        while (cur)
        {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << endl;

        ListNode* res = Solution().FindKthToTail(node1, 2);
        while (res)
        {
            cout << res->val << "->";
            res = res->next;
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete res;
        delete cur;
    }

    //BM9 删除链表的倒数第n个节点
    //https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tqId=727&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            // write code here
            //创建空结点，做表头的前继
            ListNode* res = new ListNode(-1);
            res->next = head;
            //创建pre，做慢指针的前继结点
            ListNode* pre = res;
            //创建快慢指针
            ListNode* fast = head;
            ListNode* slow = head;
            for (int i = 0; i < n; i++)
            {
                if (fast)
                {
                    fast = fast->next;
                }
            }
            while (fast)
            {
                fast = fast->next;
                pre = slow;
                slow = slow->next;

            }
            //pre为要删除的前一个结点
            pre->next = slow->next;
            return res->next;
        }
    };
    void test2()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(3);
        ListNode* node4 = new ListNode(4);
        ListNode* node5 = new ListNode(5);
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        ListNode* cur = node1;
        while (cur)
        {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << endl;
        ListNode* res = Solution2().removeNthFromEnd(node1, 2);
        while (res)
        {
            cout << res->val << "->";
            res = res->next;
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete res;
        delete cur;
    }
};


int main()
{
    lh::test1();
    lh::test2();
    return 0;
}